МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
Кафедра САПР
Розрахункова робота
з курсу:
«Методи синтезу та оптимізації»
Завдання 1.
Оптимізація виробничих планів
Формалізувати задачу, як задачу лінійного програмування (ЛП);
Записати задачу ЛП в канонічній формі;
Розв'язати дану задачу ЛП використовуючи симплекс-метод.
Їдальня підприємства має 25 кг муки, 130 шт. яєць, 16 кг маргарину, 7 кг цукрового піску і 14 кг сметани. Витрата цих продуктів на один кондитерський виріб кожного виду вказана в таблиці (в кілограмах на 1 шт.).
Вид виробу
Мука
Яйця
Маргарин
Цукровий пісок
Сметана
Бісквіт
0,2
5
0
0,2
0
Пісочний торт
0,4
0
0,6
0,10
0,5
Кекс
1/3
25/3
1/3
1/3
0
Скільки кондитерських виробів кожного виду необхідно спекти, щоб сумарна їх кількість була максимальною, а весь маргарин витрачений?
ВИКОНАННЯ РОБОТИ
Ресурси (продукти)
X1
0,2
5
0
0,2
0
X2
0,4
0
0,6
0,1
0,5
X3
0,33
8,33
0,33
0,33
0
Приймемо - кількість бісквітів, - кількість пісочних тортів та - кількість кексів.
Цільова функція - max;
;
;
;
;
.
ЗАПИС ЗАДАЧІ ЛП В КАНОНІЧНІЙ ФОРМІ
Запишемо задачу у стандартній (канонічній) формі задач лінійного програмування (ЛП).
- max.
Оскільки є чотири обмеження то введемо чотири базові змінні: , , , і запишемо обмеження у нормальній формі:
Перше обмеження:
В кінцевому вигляді:
СИМПЛЕКС-МЕТОД
Запишемо початкову симплекс-таблицю.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
1
-1
-1
-1
0
0
0
0
0
X4
0
0,2
0,4
0,33
1
0
0
0
25
- рівняння
X5
0
5
0
8,33
0
1
0
0
130
- рівняння
X6
0
0,2
0,1
0,33
0
0
1
0
7
- рівняння
X7
0
0
0,5
0
0
0
0
1
14
- рівняння
Ми можемо побачити, що в нас всі три не базові змінні мають однаковий коефіцієнт -1, тому ведучим стовпчиком буде любий, наприклад стовпчик, якому відповідає не базова змінна .
Визначаємо відношення величин стовпчика «Р» до коефіцієнтів стовпчика :
- рівняння: 25/0,2=125;
- рівняння: 130/5=26;
- рівняння: 7/0,2=35;
Отже ведучим буде рядок, який відповідає - рівняння.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
1
-1
-1
-1
0
0
0
0
0
X4
0
0,2
0,4
0,33
1
0
0
0
25
125
X5
0
5
0
8,33
0
1
0
0
130
26
X6
0
0,2
0,1
0,33
0
0
1
0
7
35
X7
0
0
0,5
0
0
0
0
1
14
Після того як визначені змінні, що включається і виключається (з використанням умов оптимальності і допустимості), наступна ітерація (пошук нового базисного рішення) здійснюється методом виключення змінних, або методом Гаусса - Жордана. Цей процес зміни базису включає наступні обчислювальні процедури двох типів.
Тип 1 (формування ведучого рівняння).
Нова ведуча стрічка = Попередня ведуча стрічка / Ведучий елемент
Тип 2 (формування всіх інших рівнянь, включаючи z-рівняння).
Нове рівняння = Попереднє рівняння – (Нова ведуча стрічка)*(Коефіцієнт ведучого стовпчика попереднього рівняння)
Застосовуючи до початкової таблиці процедуру 1, ми ділимо - рівняння на ведучий елемент, рівний 5. Так як у стовпці базисних змінних займає місце змінної , вказана процедура приводить до наступних змін початкової симплекс-таблиці.
БЗ
Z
X1
X2
X3
X4
X5
X6
X7
Р
В
Z
X4
X1
0
1
0
1,666
0
0,2
0
0
26
X6
X7
Відмітимо, що в стовпці «Р» тепер фігурує нове значення змінної (=26), яке дорівнює мінімальній величині відношень, що аналізуються при перевірці умови допустимості.
Щоб скласти нову симплекс-таблицю, виконаємо необхідні обчислювальні процедури типу 2.
1. Z - рівняння
Попереднє Z-рівняння:
( 1
-1
-1
-1
0
0
0
0
0 )
-(-1)*Нова ведуча стрічка:
( 0
1
0
1,666
0
0,2
0
0
26)
= Нове z-рівняння:
( 1
0
-1
0,666
0
0,2
0
0
26 )
2. X4-рівняння
Попереднє X4-рівняння:
( 0
0,...
